home *** CD-ROM | disk | FTP | other *** search
/ PCGUIA 127 / PC Guia 127.iso / Software / Produtividade / OpenOffice.org 2.0.1 / openofficeorg4.cab / test_bisect.py < prev    next >
Text File  |  2005-11-19  |  8KB  |  206 lines
  1. import unittest
  2. from test import test_support
  3. from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
  4.  
  5. class TestBisect(unittest.TestCase):
  6.  
  7.     precomputedCases = [
  8.         (bisect_right, [], 1, 0),
  9.         (bisect_right, [1], 0, 0),
  10.         (bisect_right, [1], 1, 1),
  11.         (bisect_right, [1], 2, 1),
  12.         (bisect_right, [1, 1], 0, 0),
  13.         (bisect_right, [1, 1], 1, 2),
  14.         (bisect_right, [1, 1], 2, 2),
  15.         (bisect_right, [1, 1, 1], 0, 0),
  16.         (bisect_right, [1, 1, 1], 1, 3),
  17.         (bisect_right, [1, 1, 1], 2, 3),
  18.         (bisect_right, [1, 1, 1, 1], 0, 0),
  19.         (bisect_right, [1, 1, 1, 1], 1, 4),
  20.         (bisect_right, [1, 1, 1, 1], 2, 4),
  21.         (bisect_right, [1, 2], 0, 0),
  22.         (bisect_right, [1, 2], 1, 1),
  23.         (bisect_right, [1, 2], 1.5, 1),
  24.         (bisect_right, [1, 2], 2, 2),
  25.         (bisect_right, [1, 2], 3, 2),
  26.         (bisect_right, [1, 1, 2, 2], 0, 0),
  27.         (bisect_right, [1, 1, 2, 2], 1, 2),
  28.         (bisect_right, [1, 1, 2, 2], 1.5, 2),
  29.         (bisect_right, [1, 1, 2, 2], 2, 4),
  30.         (bisect_right, [1, 1, 2, 2], 3, 4),
  31.         (bisect_right, [1, 2, 3], 0, 0),
  32.         (bisect_right, [1, 2, 3], 1, 1),
  33.         (bisect_right, [1, 2, 3], 1.5, 1),
  34.         (bisect_right, [1, 2, 3], 2, 2),
  35.         (bisect_right, [1, 2, 3], 2.5, 2),
  36.         (bisect_right, [1, 2, 3], 3, 3),
  37.         (bisect_right, [1, 2, 3], 4, 3),
  38.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  39.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
  40.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  41.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
  42.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  43.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
  44.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  45.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
  46.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
  47.  
  48.         (bisect_left, [], 1, 0),
  49.         (bisect_left, [1], 0, 0),
  50.         (bisect_left, [1], 1, 0),
  51.         (bisect_left, [1], 2, 1),
  52.         (bisect_left, [1, 1], 0, 0),
  53.         (bisect_left, [1, 1], 1, 0),
  54.         (bisect_left, [1, 1], 2, 2),
  55.         (bisect_left, [1, 1, 1], 0, 0),
  56.         (bisect_left, [1, 1, 1], 1, 0),
  57.         (bisect_left, [1, 1, 1], 2, 3),
  58.         (bisect_left, [1, 1, 1, 1], 0, 0),
  59.         (bisect_left, [1, 1, 1, 1], 1, 0),
  60.         (bisect_left, [1, 1, 1, 1], 2, 4),
  61.         (bisect_left, [1, 2], 0, 0),
  62.         (bisect_left, [1, 2], 1, 0),
  63.         (bisect_left, [1, 2], 1.5, 1),
  64.         (bisect_left, [1, 2], 2, 1),
  65.         (bisect_left, [1, 2], 3, 2),
  66.         (bisect_left, [1, 1, 2, 2], 0, 0),
  67.         (bisect_left, [1, 1, 2, 2], 1, 0),
  68.         (bisect_left, [1, 1, 2, 2], 1.5, 2),
  69.         (bisect_left, [1, 1, 2, 2], 2, 2),
  70.         (bisect_left, [1, 1, 2, 2], 3, 4),
  71.         (bisect_left, [1, 2, 3], 0, 0),
  72.         (bisect_left, [1, 2, 3], 1, 0),
  73.         (bisect_left, [1, 2, 3], 1.5, 1),
  74.         (bisect_left, [1, 2, 3], 2, 1),
  75.         (bisect_left, [1, 2, 3], 2.5, 2),
  76.         (bisect_left, [1, 2, 3], 3, 2),
  77.         (bisect_left, [1, 2, 3], 4, 3),
  78.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  79.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
  80.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  81.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
  82.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  83.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
  84.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  85.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
  86.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
  87.     ]
  88.  
  89.     def test_precomputed(self):
  90.         for func, data, elem, expected in self.precomputedCases:
  91.             self.assertEqual(func(data, elem), expected)
  92.  
  93.     def test_random(self, n=25):
  94.         from random import randrange
  95.         for i in xrange(n):
  96.             data = [randrange(0, n, 2) for j in xrange(i)]
  97.             data.sort()
  98.             elem = randrange(-1, n+1)
  99.             ip = bisect_left(data, elem)
  100.             if ip < len(data):
  101.                 self.failUnless(elem <= data[ip])
  102.             if ip > 0:
  103.                 self.failUnless(data[ip-1] < elem)
  104.             ip = bisect_right(data, elem)
  105.             if ip < len(data):
  106.                 self.failUnless(elem < data[ip])
  107.             if ip > 0:
  108.                 self.failUnless(data[ip-1] <= elem)
  109.  
  110.     def test_optionalSlicing(self):
  111.         for func, data, elem, expected in self.precomputedCases:
  112.             for lo in xrange(4):
  113.                 lo = min(len(data), lo)
  114.                 for hi in xrange(3,8):
  115.                     hi = min(len(data), hi)
  116.                     ip = func(data, elem, lo, hi)
  117.                     self.failUnless(lo <= ip <= hi)
  118.                     if func is bisect_left and ip < hi:
  119.                         self.failUnless(elem <= data[ip])
  120.                     if func is bisect_left and ip > lo:
  121.                         self.failUnless(data[ip-1] < elem)
  122.                     if func is bisect_right and ip < hi:
  123.                         self.failUnless(elem < data[ip])
  124.                     if func is bisect_right and ip > lo:
  125.                         self.failUnless(data[ip-1] <= elem)
  126.                     self.assertEqual(ip, max(lo, min(hi, expected)))
  127.  
  128.     def test_backcompatibility(self):
  129.         self.assertEqual(bisect, bisect_right)
  130.  
  131. #==============================================================================
  132.  
  133. class TestInsort(unittest.TestCase):
  134.  
  135.     def test_vsListSort(self, n=500):
  136.         from random import choice
  137.         digits = "0123456789"
  138.         raw = []
  139.         insorted = []
  140.         for i in range(n):
  141.             digit = choice(digits)
  142.             raw.append(digit)
  143.             if digit in "02468":
  144.                 f = insort_left
  145.             else:
  146.                 f = insort_right
  147.             f(insorted, digit)
  148.         sorted = raw[:]
  149.         sorted.sort()
  150.         self.assertEqual(sorted, insorted)
  151.  
  152.     def test_backcompatibility(self):
  153.         self.assertEqual(insort, insort_right)
  154.  
  155. #==============================================================================
  156.  
  157. libreftest = """
  158. Example from the Library Reference:  Doc/lib/libbisect.tex
  159.  
  160. The bisect() function is generally useful for categorizing numeric data.
  161. This example uses bisect() to look up a letter grade for an exam total
  162. (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
  163. 75..84 is a `B', etc.
  164.  
  165.     >>> grades = "FEDCBA"
  166.     >>> breakpoints = [30, 44, 66, 75, 85]
  167.     >>> from bisect import bisect
  168.     >>> def grade(total):
  169.     ...           return grades[bisect(breakpoints, total)]
  170.     ...
  171.     >>> grade(66)
  172.     'C'
  173.     >>> map(grade, [33, 99, 77, 44, 12, 88])
  174.     ['E', 'A', 'B', 'D', 'F', 'A']
  175.  
  176. The bisect module can be used with the Queue module to implement
  177. a priority queue (example courtesy of Fredrik Lundh):
  178.  
  179. >>> import Queue, bisect
  180. >>> class PriorityQueue(Queue.Queue):
  181. ...     def _put(self, item):
  182. ...         bisect.insort(self.queue, item)
  183. ...
  184. >>> queue = PriorityQueue(0)
  185. >>> queue.put((2, "second"))
  186. >>> queue.put((1, "first"))
  187. >>> queue.put((3, "third"))
  188. >>> queue.get()
  189. (1, 'first')
  190. >>> queue.get()
  191. (2, 'second')
  192.  
  193. """
  194.  
  195. #------------------------------------------------------------------------------
  196.  
  197. __test__ = {'libreftest' : libreftest}
  198.  
  199. def test_main(verbose=None):
  200.     from test import test_bisect
  201.     test_support.run_unittest(TestBisect, TestInsort)
  202.     test_support.run_doctest(test_bisect, verbose)
  203.  
  204. if __name__ == "__main__":
  205.     test_main(verbose=True)
  206.